Analisis Struktur Data dan Algoritma Python (Edisi 2): Pemodelan Teori Graf: Dari Dunia Nyata ke Struktur Data Abstrak

Pemodelan teori graf adalah proses mengabstraksikan hubungan kompleks dunia nyata (seperti rute internet atau transisi status) menjadi objek matematis $G = (V, E)$. Dengan mendefinisikan entitas sebagaisimpul (Vertex) dan hubungan sebagaisisi (Edge)kita dapat menggunakan tipe data abstrak (ADT) dan algoritma yang seragam untuk menyelesaikan berbagai masalah.

Definisi Komponen Inti

simpul (Vertex): Juga disebut simpul. Memiliki "kunci" (Key) sebagai identifikasi unik dan dapat membawa "muatan" (Payload).
sisi (Edge): Menghubungkan dua simpul, menunjukkan adanya hubungan di antaranya. Bisa bersifat satu arah (graf berarah) atau dua arah.
Bobot (Weight): 边上的数值，代表成本（如距离、延迟、带宽）。

Ketelitian Matematis

Secara matematis, $G = (V, E)$. Di mana $V$ adalah himpunan simpul, dan $E$ adalah himpunan sisi berupa pasangan terurut $(v, w)$, dengan $v, w \in V$. Struktur abstrak yang sangat tinggi ini memungkinkan kita menggunakan algoritma BFS/DFS yang sama untuk menyelesaikan berbagai masalah mulai dari navigasi peta hingga rekomendasi jejaring sosial.

Wawasan Pemodelan: Graf Ruang Status

Dalam menyelesaikan teka-teki logika (seperti masalah ember air), setiapstatus sahadalah simpul, dan setiapoperasi sahadalah sisi. Proses menyelesaikan masalah adalah mencari jalur dari simpul awal ke simpul tujuan.

Tantangan Pemodelan Logika: Masalah Ember Air (Tugas Menulis)

Memetakan status logika ke struktur graf

Anda memiliki dua ember dengan kapasitas 4 galon dan 3 galon, tanpa tanda ukur. Anda bisa mengisi penuh, menuangkan kosong, atau menuangkan saling-menyala. Tugas: membuat ember 4 galon akhirnya berisi 2 galon air.

Tulis program atau deskripsikan logika pemodelannya untuk menyelesaikan masalah ini. (Persyaratan: keluaran minimal 150 kata deskripsi logika atau implementasi kode)

Jawaban:
模型方案： 1. 顶点定义：使用元组 (v4, v3) 表示状态，其中 v4 为 4加仑坛子的水量，v3 为 3加仑坛子的水量。初始顶点为 (0,0)，目标顶点为 (2, x)。 2. 边定义：合法的操作（灌满、倒空、转移）构成边。例如 (0,0) -> (4,0) 是“灌满4加仑”的操作。 3. 解决步骤： - (0,0) -> (0,3) : 灌满3加仑 - (0,3) -> (3,0) : 倒入4加仑坛子 - (3,0) -> (3,3) : 再次灌满3加仑 - (3,3) -> (4,2) : 灌满4加仑坛子，此时3加仑坛子剩下2加仑 - (4,2) -> (0,2) : 倒空4加仑坛子 - (0,2) -> (2,0) : 将3加仑坛子中的2加仑倒入4加仑坛子，达成目标。

Pemodelan Skenario: Zebra dan Singa Menyeberangi Sungai (Tugas Menulis)

Pencarian Jalur dalam Kondisi Kendala

3 zebra dan 3 singa siap menyeberangi sungai, kapasitas perahu hanya 2. Jika jumlah singa lebih besar daripada zebra di salah satu tepi sungai, zebra akan dimakan. Temukan cara aman menyeberang.

Jelaskan pendekatan pemodelan graf untuk masalah ini serta satu jalur yang layak. (Persyaratan: keluaran minimal 120 kata)

Jawaban:
建模逻辑： 1. 状态表示：(A_left, L_left, boat_pos)，分别代表左岸羚羊数、狮子数和船的位置（0左1右）。 2. 约束条件：A_left == 0 或 A_left >= L_left，且右岸同样满足此条件。 3. 路径序列： - (3,3,0) -> (3,1,1) : 运2狮子到右岸 - (3,1,1) -> (3,2,0) : 回1狮子 - (3,2,0) -> (3,0,1) : 运剩下2狮子到右岸 - (3,0,1) -> (3,1,0) : 回1狮子 - (3,1,0) -> (1,1,1) : 运2羚羊到右岸 - (1,1,1) -> (2,2,0) : 回1羚羊1狮子 - (2,2,0) -> (0,2,1) : 运最后2羚羊到右岸 - (0,2,1) -> (0,3,0) : 回1狮子 - (0,3,0) -> (0,1,1) : 运2狮子到右岸 - (0,1,1) -> (0,2,0) : 回1狮子 - (0,2,0) -> (0,0,1) : 全员到达右岸。

Analisis Kompleksitas dan Struktur (Jawaban Pendek)

Dasar Teori Algoritma

分析 buildGraph 函数（根据代码清单 7-2）的时间复杂度。

Jawaban:
Kompleksitas waktu buildGraph adalah O(V + E). Di mana V adalah jumlah simpul, dan E adalah jumlah sisi (atau hubungan kata). Operasi addVertex adalah O(1), operasi addEdge melibatkan pencarian kamus juga rata-rata O(1), sehingga total waktu berhubungan linier dengan skala input.

Berdasarkan matriks ketetanggaan berikut, gambar struktur graf yang sesuai: A-B:7, A-C:5, A-F:1, B-D:7, B-E:3, C-B:2, C-F:8, D-E:2, E-D:5, F-C:1.

Jawaban:
Deskripsi Struktur Graf: - Himpunan simpul V = {A, B, C, D, E, F} - Himpunan sisi berarah berbobot E = { (A,B,7), (A,C,5), (A,F,1), (B,D,7), (B,E,3), (C,B,2), (C,F,8), (D,E,2), (E,D,5), (F,C,1) } Ini adalah graf berarah berbobot dengan siklus yang kompleks.